package LintCode;

/**
 * 给一个n*m大小的矩阵，寻找矩阵中所有比邻居（上下左右，对角也算，不考虑边界，即8个）都严格大的点。
 * 返回一个n*m大小的矩阵，如果原矩阵中的点比邻居都严格大，则该位置为1，反之为0。
 *
 * 1 \leq n,m \leq 1001≤n,m≤100
 *
 * 样例
 * 样例 1
 *
 * 输入:
 * 1 2 3
 * 4 5 8
 * 9 7 0
 * 输出:
 * 0 0 0
 * 0 0 1
 * 1 0 0
 */

public class FindMaxPoint {

    public static void main(String[] args) {
        int a[][] = {{1,2,3,4},{5,5,5,2},{1,1,1,1},{0,0,0,9}};

        for (int i = 0 ; i < a.length ; i++){
            for(int j = 0 ; j < a[i].length ; j++){
                System.out.print(a[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println();

        FindMaxPoint solution = new FindMaxPoint();
        int b[][] = solution.highpoints(a);

        for (int i = 0 ; i < b.length ; i++){
            for(int j = 0 ; j < b[i].length ; j++){
                System.out.print(b[i][j]+" ");
            }
            System.out.println();
        }

    }


    /**
     * @param grid: a matrix
     * @return: Find all points that are strictly larger than their neighbors
     */
    public int[][] highpoints(int[][] grid) {
        int [][]answer = new int[grid.length][grid[0].length];
        FindMaxPoint solution = new FindMaxPoint();
        solution.solve(grid,answer);
        return answer;
    }

    public void solve(int [][]g,int [][]s){
        int n = g.length;
        for (int i = 0;i < n;i++){

            int m = g[i].length;

            for (int j = 0;j < m;j++){
                boolean flag = true;
                int a = i + 1;//下
                int b = i - 1;//上
                int c = j + 1;//右
                int d = j - 1;//左
                int now = g[i][j];//中

                if ( b >= 0){//上一层

                    if(now <= g[b][j]){//上
                        flag = false;
                    }

                    if(c < m && now <= g[b][c]){//上右
                        flag = false;
                    }

                    if( d >= 0 && now <= g[b][d]){//上左
                        flag = false;
                    }

                }

                if ( a < n){//下一层

                    if(now <= g[a][j]){//下
                        flag = false;
                    }

                    if(c < m && now <= g[a][c]){//下右
                        flag = false;
                    }

                    if(d >= 0 && (now <= g[a][d]) ){//下左
                        flag = false;
                    }

                }

                if(c < m && (now <= g[i][c]) ){//同一层的右
                    flag = false;
                }

                if(d >= 0 && (now <= g[i][d]) ){//同一层的左
                    flag = false;
                }

                if (flag){
                    s[i][j] = 1;
                }else{
                    s[i][j] = 0;
                }

            }
        }

    }

}